package leetcode.jianzhioffer;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-11-05 21:25
 **/
public class JianZhiOffer45 {

    public static void main(String[] args) {
        JianZhiOffer45 offer = new JianZhiOffer45();
        int[] nums = {1,2,3,4,5,6,7,8,9,0};
        System.out.println(offer.minNumber(nums));
    }

    public String minNumber(int[] nums) {
        if (nums.length == 1) {
            return String.valueOf(nums[0]);
        }
        String[] strs = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            strs[i] = String.valueOf(nums[i]);
        }
        quickSort(strs, 0, nums.length - 1);
        StringBuilder builder = new StringBuilder();
        for (String str : strs) {
            builder.append(str);
        }
        return builder.toString();
    }


    private static void quickSort(String[] strs, int low, int high) {
        if (low >= high) {
            return;
        }
        int i = low;
        int j = high;
        String temp = strs[i];
        while (i < j) {
            while ((strs[j] + temp).compareTo(temp + strs[j]) >= 0 && i < j) {
                j--;
            }

            if (i < j) {
                strs[i] = strs[j];
            }

            while ((strs[i] + temp).compareTo(temp + strs[i]) <= 0 && i < j) {
                i++;
            }

            if (i < j) {
                strs[j] = strs[i];
            }
        }
        strs[i] = temp;
        quickSort(strs, low, i - 1);
        quickSort(strs, i + 1, high);
    }

}
